from .Heap import Heap


class GHeap(Heap):
    def __init__(self, items):
        super().__init__(items)
        self.build()

    def getValue(self, index):
        return self.items[index]

    def heapify(self, index):

        left_index = self.left(index)
        right_index = self.right(index)


        if left_index < self.size-1 and self.getValue(left_index) > self.getValue(index):
            gt = left_index
        else:
            gt = index

        if right_index < self.size-1 and self.getValue(right_index) > self.getValue(gt):
            gt = right_index

        if gt != index:
            self.items[index], self.items[gt] = self.items[gt], self.items[index]
            self.heapify(gt)


    def insert(self, item):
        # O(log(n))
        self.items.append(item)
        leaf = len(self.items) - 1
        node = self.parent(leaf)
        while node >= 0:
            if self.getValue(node) < self.getValue(leaf):
                self.items[node], self.items[leaf] = self.items[leaf], self.items[node]
                leaf = node
                node = self.parent(node)
            else:
                break

    def pop(self):
        # O(log(n))
        last = len(self.items) - 1
        if last < 0:
            return None
        self.items[0], self.items[last] = self.items[last], self.items[0]
        val = self.items.pop()
        self.heapify(0)
        return val



